import java.util.*;

class Solution210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(prerequisites.length <= 0) {
            int[] arr = new int[numCourses] ;
            for(int i=0 ; i < numCourses ; i ++){
                arr[i] = i ;
            }
            return arr ;
        }
        int len = prerequisites.length ;
        // 记录拓扑排序
        List<Integer> sum = new ArrayList<>() ;
        // 记录元素入度
        int[] rudu = new int[numCourses] ;
        //  记录 元素 的各个 指向的对象(出度)
        Map<Integer, List<Integer>> map = new HashMap<>() ;
        for(int i=0 ; i <len ; i ++){
            int a = prerequisites[i][0] ;
            int  b = prerequisites[i][1] ;
            rudu[a] ++ ;
            if(map.containsKey(b)){
                map.get(b).add(a) ;
            }else{
                map.put(b , new ArrayList<Integer>() );
                map.get(b).add(a) ;
            }
        }
        Queue<Integer> queue = new LinkedList<>() ;
        // 如果元素的入度是0, 就入队列
        for(int i=0 ; i < numCourses ; i ++){
            if(rudu[i] == 0){
                queue.add(i) ;
            }
        }
        //bfs
        while(!queue.isEmpty()){
            int ret = queue.poll() ;
            List<Integer> li  = map.get(ret) ;
            if(li != null){
                for(int j : li){
                    // 删除掉指向的边, 所以 指向元素 的入度要-1
                    rudu[j]-- ;
                    // 如果 删除边后 , 指向元素的入度为0了, 就入队列
                    if(rudu[j] == 0){
                        queue.add(j) ;
                    }
                }
            }
            sum.add(ret) ;
        }
        // bfs结束后
        // 最后如果 有向图里有环(也就是还有元素的入度不为0, 就是 返回false)
        for(int i : rudu){
            if(i != 0){
                return new int[]{} ;
            }
        }
        int[] tar = new int[sum.size()] ;
        // 如果无环, 返回结构 (拓扑排序结构)
        for(int i=0 ; i < sum.size() ; i ++){
            tar[i] = sum.get(i) ;
        }
        return tar ;
    }
}